//在什么情况下，插入排序的工作量会比较小？
//首先，当数组元素较少的时候，插入排序的工作量会比较小。因为插入排序的时间复杂度是O(n2)，工作量和n2成正比，如果n比较小，那么排序的工作量自然会小得多。
//其次，当数组大部分元素有序的时候，插入排序的工作量也会相对较小。因为在这种情况下，数组中的元素并不需要进行频繁的比较和交换。”


//逐步分组进行粗调，再进行直接插入排序的思想，就是希尔排序。

//为了保证分组粗调没有盲区，每一轮的增量需要彼此“互质”，也就是没有除1之外的公约数。”


function shellSort(array) {
    //希尔排序的增量
    let d = array.length;

    while (d > 1) {
        //使用希尔增量的方式，即每次折半
        d = d / 2;
        for (let x = 0; x < d; x++) {
            for (let i = x + d; i < array.length; i = i + d) {
                let temp = array[i];
                let j;
                for (j = i - d; (j >= 0) && (array[j] > temp); j = j - d) {
                    array[j + d] = array[j];
                }
                array[j + d] = temp;
            }
        }
    }
    return array;
}

let array = [ 5, 3, 9, 12, 6, 1, 7, 2, 4, 11, 8, 10 ];
console.log(shellSort(array))
console.log(array.length)